<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Binary search tree',
	'<{subtitle}>' => 'Written in <span title="Data Structures">CS 3303</span> by <a href="https://y.st./">Alexand(er|ra) Yst</a>, finalised on 2018-12-12',
	'<{copyright year}>' => '2018',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<p>
	Below is the code for my submission.
	If you&apos;re running it in Jeliot, please read the output in the console at the bottom of the Jeliot window, as it&apos;ll give you instructions of what to do next.
	There&apos;s no way for me to add the instructions to the input box, which Jeliot puts at the top of the window instead.
</p>
<p>
	Unfortunately, we didn&apos;t cover methods of keeping binary trees balanced as items are added this week.
	As a result, the tree implemented in my code puts new nodes in the places they belong, but doesn&apos;t do any rebalancing afterwards.
	Nodes are added in the first available spot in which their location is consistent with the path used to get there.
	Search time is therefore about O(n) in the worst case, with n being the number of integers in the tree, as there tree might end up as one long chain of branches with a leaf on the end and we may be searching for the value in that leaf or a value not in the tree that would be a child of that leaf.
	In best-case situations, we have no tree to search at all, as the user entered no integers to populate it with.
	In that case, search time is Ω(0).
</p>
<p>
	Without further ado, the code:
</p>
<blockquote>
<pre><code>/**
 * CS 3303 Unit 4 binary search tree assignment submission
 * Copyright © 2018 Alex Yst &lt;mailto:copyright@y.st&gt;
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see &lt;https://www.gnu.org./licenses/&gt;.
**/

public class Node {
	Node left;
	Node right;
	int value;
	public Node(int value) {
		this.value = value;
	}
	public void Insert(int i) {
		if(i &lt; this.value) {
			if(this.left == null) {
				this.left = new Node(i);
			} else {
				this.left.Insert(i);
			}
		} else if(i &gt; this.value) {
			if(this.right == null) {
				this.right = new Node(i);
			} else {
				this.right.Insert(i);
			}
		}
// The third option is that the new value is equal to this node&apos;s
// value. We can optimise based on our use case though. We don&apos;t need
// to know how many numbers the user entered or even know how many
// times a user entered a given number. We only need to know *if* a
// given number had been entered. That means that if the value already
// appears in the tree, we do not need to add it again. Basically, the
// tree in this assignment represents an ordered set, not an ordered
// list.
	}
}

public class Tree {
	Node pointer;
	public void Insert(int i) {
		if(this.pointer != null) {
			this.pointer.Insert(i);
		} else {
			this.pointer = new Node(i);
		}
	}
}

public class Unit4 {
	public static void main(String[] args) {
		java.util.Scanner scanner = new java.util.Scanner(System.in);
		Tree tree = new Tree();
		System.out.println(&quot;Enter any integer to add the next number to the tree.&quot;);
		System.out.println(&quot;Alternatively, enter a non-integer to finalise the tree.&quot;);
		System.out.println(&quot;Entering \&quot;Done.\&quot; or a blank line, for example, will end the integer-entering process.&quot;);
// We don&apos;t know if the value entered by the user is an integer or not.
// If it&apos;s not, an exception will be thrown. We can take advantage of
// that by continuously asking for integers until the user enters a
// non-integer value, causing an exception to be thrown. We&apos;ll discard
// the exception at that point, but the throwing of said exception will
// break us out of the loop in the &quot;try&quot; block.
		try {
			while(true) {
				String next = scanner.next();
				tree.Insert(java.lang.Integer.parseInt(next));
			}
		} catch(Exception e) {
			System.out.println(&quot;Please enter an integer to search the tree for:&quot;);
// Searching for a needle in a haystack ...
			int needle = scanner.nextInt();
			int count = 0;
			Node current = tree.pointer;
			boolean found = false;
			while(current != null) {
				count++;
				if(current.value &lt; needle) {
					current = current.left;
				} else if(current.value &lt; needle) {
					current = current.right;
				} else {
					found = true;
					current = null;
				}
			}
			if(found) {
				System.out.println(&quot;The value was found in &quot; + count + &quot; iteration(s).&quot;);
			} else {
				System.out.println(count + &quot; iteration(s) were performed, but the value was not found.&quot;);
			}
		}
	}
}</code></pre>
</blockquote>
END
);
